package q72_minDistance;

public class Solution {
    public int minDistance(String word1, String word2) {
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for (int i = 0; i < word1.length() + 1; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j < word2.length() + 1; j++) {
            dp[0][j] = j;
        }

        for (int i = 1; i <= word1.length(); i++) {
            for (int j = 1; j <= word2.length(); j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    // 如果此处相同 则不需要加步数
                    dp[i][j] = dp[i - 1][j - 1];
                }else {
                    /*
                    此题的关键在于
                    如果不相同时 dp[i][j]应该从哪个位置加几个步骤来获得
                    首先考虑上和左
                    1 word1删除⼀个元素，那么就是以下标i - 2为结尾的word1 与 j-1为结尾的word2的最近编 辑距离 再加上⼀个操作
                    2 word2删除⼀个元素，那么就是以下标i - 1为结尾的word1 与 j-2为结尾的word2的最近编 辑距离 再加上⼀个操作
                    也就是Math.min(dp[i - 1][j], dp[i][j - 1]) + 1
                    如何考虑添加元素？
                    实际上 如果我们在w1中删除了一个元素 也就相当于在w2中添加了一个元素
                    所以实际上添加与删除两者是一样的

                    最后考虑替换元素
                    替换元素意味着当前dp[i][j]来自于dp[i - 1][j - 1]加一个替换步骤 此时不考虑i- 1和j - 1两个位置是什么字符
                    只考虑替换带来的一个步骤即可
                    因此公式：
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                     */
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
            }
        }

        return dp[word1.length()][word2.length()];
    }
}
